The problem can be found at the following link: Question Link
To solve this problem, I implemented an in-order traversal of the binary search tree (BST) to get the elements in sorted order.
- Then, I used an ordered set (a data structure provided by the GNU C++ pb_ds library) to efficiently keep track of elements encountered so far and calculate the distance of each element from its expected position in a sorted array.
- This distance represents the number of elements smaller than the current element that have been encountered so far but should appear after it in a sorted array, violating the BST property.
- Time Complexity: The time complexity of this approach is
O(n * log(n))
, where n is the number of nodes in the binary search tree. - Auxiliary Space Complexity: The auxiliary space complexity is
O(n)
, where n is the number of nodes in the binary search tree.
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update>
class Solution {
public:
vector<int> order;
void InOrder(Node *root){
if (!root)
return;
InOrder(root->left);
order.push_back(root->data);
InOrder(root->right);
}
int pairsViolatingBST(int n, Node *root)
{
InOrder(root);
int cnt = 0;
ordered_set st;
for (int i = 0; i < n; ++i){
int distance = i - st.order_of_key(order[i]);
st.insert(order[i]);
cnt += distance;
}
return cnt;
}
};
For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.
If you find this solution helpful, consider supporting us by giving a ⭐ star
to the getlost01/gfg-potd repository.